package sort

// QuickSortPrac 快速
func QuickSortPrac(in []int) []int {
	if len(in) <= 1 {
		return in
	}
	pivot := in[0]
	left, right := make([]int, 0), make([]int, 0)
	for i := 1; i < len(in); i++ {
		if in[i] > pivot {
			right = append(right, in[i])
		} else {
			left = append(left, in[i])
		}
	}
	left = QuickSortPrac(left)
	right = QuickSortPrac(right)
	return append(append(left, pivot), right...)
}

// MergeSortPrac 归并排序
func MergeSortPrac(in []int) []int {
	if len(in) <= 1 {
		return in
	}
	mid := len(in) / 2
	return doMerge(in[:mid], in[mid:])
}

func doMerge(left []int, right []int) []int {
	l, r := 0, 0
	result := make([]int, 0)
	for l < len(left) && r < len(right) {
		if left[l] < right[r] {
			result = append(result, left[l])
			l++
		} else {
			result = append(result, right[r])
			r++
		}
	}
	result = append(result, left[l:]...)
	result = append(result, right[r:]...)
	return result
}

func insertionSortPrac(in []int) []int {
	for i := 1; i < len(in); i++ {
		current := in[i]
		prave := i - 1
		for prave >= 0 && current < in[prave] {
			in[prave+1] = in[prave]
			prave--
		}
		in[prave+1] = current
	}
	return in
}

func bubbleSortPrac(in []int) []int {
	for i := 0; i < len(in); i++ {
		for j := 0; j < len(in)-i; j++ {
			if in[j] > in[j+1] {
				in[j+1], in[j] = in[j], in[j+1]
			}
		}
	}
	return in
}
